#!/usr/bin/env python3
"""
动态规划资源收集路径规划器
任务2：计算从起点到终点的最优资源收集路径，避开陷阱，优先拾取资源

核心算法：
- 状态定义：dp[i][j] 表示走到坐标(i,j)时的最大资源值
- 状态转移：dp[i][j] = max(dp[prev_i][prev_j]) + resource[i][j]
- 优化目标：最大化资源收集值，同时避开陷阱
- 路径重构：使用父节点记录重构最优路径序列

特性：
- 支持任意迷宫布局
- 智能避开陷阱（-3惩罚）
- 优先收集高价值资源
- 完整路径可视化
"""

import json
from typing import List, Tuple, Dict, Optional
from heapq import heappush, heappop
from collections import deque


class ResourcePathPlanner:
    """动态规划资源收集路径规划器"""
    
    def __init__(self):
        """初始化路径规划器"""
        self.maze: Optional[List[List[str]]] = None
        self.size = 0
        self.resources: Dict[Tuple[int, int], int] = {}
        self.traps: List[Tuple[int, int]] = []
        self.start_pos: Optional[Tuple[int, int]] = None
        self.exit_pos: Optional[Tuple[int, int]] = None
        self.resource_matrix: Optional[List[List[float]]] = None
        self.dp: Optional[List[List[float]]] = None
        self.parent: Optional[List[List[Optional[Tuple[int, int]]]]] = None
        
    def setup_environment(self, 
                         maze_matrix: List[List[str]], 
                         resources: Dict[Tuple[int, int], int],
                         traps: List[Tuple[int, int]],
                         start_pos: Tuple[int, int],
                         exit_pos: Tuple[int, int]):
        """
        设置环境参数
        
        参数：
        maze_matrix: 迷宫矩阵 ('#' 表示墙壁, ' ' 表示通道)
        resources: 资源分布 {(x, y): value}
        traps: 陷阱位置列表 [(x, y)]，每个陷阱造成-3损失
        start_pos: 起点坐标 (x, y)
        exit_pos: 终点坐标 (x, y)
        """
        self.maze = maze_matrix
        self.size = len(maze_matrix)
        self.resources = resources
        self.traps = traps
        self.start_pos = start_pos
        self.exit_pos = exit_pos
        
        # 创建资源值矩阵
        self.resource_matrix = self._create_resource_matrix()
        
        print(f"环境设置完成:")
        print(f"- 迷宫大小: {self.size}x{self.size}")
        print(f"- 资源点数量: {len(self.resources)}")
        print(f"- 陷阱数量: {len(self.traps)}")
        print(f"- 起点: {self.start_pos}")
        print(f"- 终点: {self.exit_pos}")
        
    def _create_resource_matrix(self) -> List[List[float]]:
        """
        创建资源值矩阵
        
        返回：
        resource_matrix[i][j] 表示位置(i,j)的资源值
        - 普通通道: 0
        - 资源点: 正值
        - 陷阱: -3
        - 墙壁: -∞ (不可通过)
        """
        assert self.maze is not None
        matrix = [[0.0 for _ in range(self.size)] for _ in range(self.size)]
        
        # 设置资源值
        for (x, y), value in self.resources.items():
            if 0 <= x < self.size and 0 <= y < self.size:
                matrix[x][y] = float(value)
                
        # 设置陷阱值（-3惩罚）
        for x, y in self.traps:
            if 0 <= x < self.size and 0 <= y < self.size:
                matrix[x][y] = -3.0
                
        # 墙壁设置为负无穷（不可通过）
        for i in range(self.size):
            for j in range(self.size):
                if self.maze[i][j] == '#':
                    matrix[i][j] = float('-inf')
                    
        return matrix
    def find_optimal_path(self) -> Tuple[float, List[Tuple[int, int]]]:
        """
        使用动态规划找到最优资源收集路径
        
        算法核心：
        1. 使用修改的Dijkstra算法处理复杂迷宫路径
        2. 优先队列保证每次处理当前最优状态
        3. DP状态：dp[i][j] = 到达(i,j)的最大资源值
        4. 路径重构：通过parent矩阵回溯最优路径
        
        返回：
        (最大资源值, 最优路径序列)
        """
        if not self.maze:
            raise ValueError("请先调用setup_environment设置环境")
            
        assert self.maze is not None
        assert self.start_pos is not None  
        assert self.exit_pos is not None
        assert self.resource_matrix is not None
            
        print("\n开始动态规划资源收集路径规划...")
        
        # 初始化DP状态矩阵
        self.dp = [[float('-inf') for _ in range(self.size)] for _ in range(self.size)]
        self.parent = [[None for _ in range(self.size)] for _ in range(self.size)]
        
        # 优先队列：(-资源值, x, y) 使用负值因为heapq是最小堆
        pq = []
        start_x, start_y = self.start_pos
        
        # 初始化起点
        start_resource = self.resource_matrix[start_x][start_y]
        self.dp[start_x][start_y] = start_resource
        heappush(pq, (-start_resource, start_x, start_y))
        
        # 四个方向：上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        processed = set()
        
        while pq:
            neg_current_resource, x, y = heappop(pq)
            current_resource = -neg_current_resource
            
            # 避免重复处理
            if (x, y) in processed:
                continue
            processed.add((x, y))
            
            # 到达终点
            if (x, y) == self.exit_pos:
                print(f"找到最优路径！最大资源值: {current_resource}")
                break
                
            # 探索四个方向的邻居
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                
                # 检查边界和可通过性
                if (0 <= nx < self.size and 0 <= ny < self.size and 
                    self.resource_matrix[nx][ny] != float('-inf') and
                    (nx, ny) not in processed):
                    
                    # 计算新的累积资源值
                    new_resource = current_resource + self.resource_matrix[nx][ny]
                    
                    # 如果找到更优路径，更新状态
                    if new_resource > self.dp[nx][ny]:
                        self.dp[nx][ny] = new_resource
                        self.parent[nx][ny] = (x, y)
                        heappush(pq, (-new_resource, nx, ny))
        
        # 重构最优路径
        path = self._reconstruct_path()
        max_resource = self.dp[self.exit_pos[0]][self.exit_pos[1]]
        
        if max_resource == float('-inf'):
            print("警告：无法到达终点！")
            return 0.0, []
            
        return max_resource, path
    
    def _reconstruct_path(self) -> List[Tuple[int, int]]:
        """
        重构最优路径序列
        
        返回：
        从起点到终点的最优路径坐标序列
        """
        assert self.parent is not None and self.exit_pos is not None and self.start_pos is not None
        path = []
        current = self.exit_pos
        
        # 从终点开始回溯到起点
        while current is not None:
            path.append(current)
            if current == self.start_pos:
                break
            current = self.parent[current[0]][current[1]]
            
        # 反转得到从起点到终点的路径
        path.reverse()
        return path
    
    def visualize_path(self, path: List[Tuple[int, int]]) -> List[List[str]]:
        """
        可视化最优路径
        
        符号说明：
        - S: 起点 (Start)
        - E: 终点 (Exit)  
        - R: 低价值资源 (1-5分)
        - G: 中价值资源 (6-9分)  
        - H: 高价值资源 (10+分)
        - T: 陷阱 (Trap)
        - ●: 路径经过点
        - #: 墙壁
        - ' ': 未经过的通道
        
        返回：
        可视化后的迷宫矩阵
        """
        assert self.maze is not None
        # 深拷贝原始迷宫
        visual_matrix = [row[:] for row in self.maze]
        
        # 标记路径上的每个点
        path_positions = set(path)
        
        for i, (x, y) in enumerate(path):
            if (x, y) == self.start_pos:
                visual_matrix[x][y] = 'S'
            elif (x, y) == self.exit_pos:
                visual_matrix[x][y] = 'E'
            elif (x, y) in self.resources:
                # 根据资源价值使用不同符号
                value = self.resources[(x, y)]
                if value >= 10:
                    visual_matrix[x][y] = 'H'  # 高价值资源
                elif value >= 6:
                    visual_matrix[x][y] = 'G'  # 中价值资源
                else:
                    visual_matrix[x][y] = 'R'  # 低价值资源
            elif (x, y) in self.traps:
                visual_matrix[x][y] = 'T'
            else:
                visual_matrix[x][y] = '●'
                
        return visual_matrix
    
    def print_maze_with_path(self, visual_matrix: List[List[str]]):
        """打印带路径的迷宫"""
        print("\n=== 最优路径可视化 ===")
        print("图例: S=起点, E=终点, R=低价值资源(1-5), G=中价值资源(6-9), H=高价值资源(10+), T=陷阱(-3), ●=路径, #=墙壁")
        print()
        
        for row in visual_matrix:
            print(''.join(f'{cell:>3}' for cell in row))
    
    def analyze_path(self, max_resource: float, path: List[Tuple[int, int]]):
        """
        分析最优路径的详细信息
        
        包括：
        - 基本路径信息
        - 资源收集详情
        - 陷阱遭遇情况
        - 收集效率分析
        """
        print(f"\n=== 动态规划资源收集路径分析 ===")
        print(f"起点: {self.start_pos}")
        print(f"终点: {self.exit_pos}")
        print(f"最优资源收集值: {max_resource:.1f}")
        print(f"路径长度: {len(path)} 步")
        
        # 分析路径收集情况
        resources_collected = []
        traps_hit = []
        total_steps = len(path)
        
        for step, (x, y) in enumerate(path):
            if (x, y) in self.resources:
                resources_collected.append(((x, y), self.resources[(x, y)], step))
            elif (x, y) in self.traps:
                traps_hit.append(((x, y), step))
        
        print(f"\n收集到的资源: {len(resources_collected)} 个")
        for pos, value, step in resources_collected:
            print(f"  第{step:2d}步 位置{pos}: +{value}")
            
        print(f"\n遇到的陷阱: {len(traps_hit)} 个")
        for pos, step in traps_hit:
            print(f"  第{step:2d}步 位置{pos}: -3")
        
        # 计算各种统计信息
        total_resource_value = sum(value for _, value, _ in resources_collected)
        total_trap_penalty = len(traps_hit) * 3
        net_gain = total_resource_value - total_trap_penalty
        
        print(f"\n=== 收益分析 ===")
        print(f"资源总价值: +{total_resource_value}")
        print(f"陷阱总惩罚: -{total_trap_penalty}")
        print(f"净收益: {net_gain}")
        print(f"最终累积资源值: {max_resource:.1f}")
        
        # 计算效率指标
        total_available_resources = sum(self.resources.values())
        if total_available_resources > 0:
            collection_efficiency = (total_resource_value / total_available_resources) * 100
            print(f"资源收集效率: {collection_efficiency:.1f}%")
            
        # 路径效率（相对于曼哈顿距离）
        assert self.exit_pos is not None and self.start_pos is not None
        manhattan_distance = abs(self.exit_pos[0] - self.start_pos[0]) + abs(self.exit_pos[1] - self.start_pos[1])
        if manhattan_distance > 0:
            path_efficiency = (manhattan_distance / (total_steps - 1)) * 100
            print(f"路径效率: {path_efficiency:.1f}% (相对于曼哈顿距离)")


def load_maze_from_json(filename: str) -> List[List[str]]:
    """从JSON文件加载迷宫"""
    with open(filename, 'r', encoding='utf-8') as f:
        data = json.load(f)
    return data['maze']


def demo_resource_planning():
    """演示动态规划资源收集路径规划"""
    print("=== 动态规划资源收集路径规划演示 ===\n")
    
    # 创建规划器
    planner = ResourcePathPlanner()
    
    # 测试用例1：7x7迷宫
    print("【测试用例1】7x7 迷宫资源收集")
    try:
        maze_7x7 = load_maze_from_json('perfect_maze_7x7.json')
        
        # 定义资源分布（高价值资源分散放置）
        resources_7x7 = {
            (1, 3): 5,    # 高价值资源
            (3, 1): 3,    # 中等价值资源
            (3, 5): 4,    # 中等价值资源
            (5, 3): 6,    # 最高价值资源
            (2, 4): 2,    # 低价值资源
        }
        
        # 定义陷阱位置
        traps_7x7 = [
            (2, 2),       # 路径上的陷阱
            (4, 4),       # 另一个陷阱
        ]
        
        # 设置环境
        planner.setup_environment(
            maze_matrix=maze_7x7,
            resources=resources_7x7,
            traps=traps_7x7,
            start_pos=(1, 1),
            exit_pos=(5, 5)
        )
        
        # 寻找最优路径
        max_resource, optimal_path = planner.find_optimal_path()
        
        # 可视化结果
        visual_matrix = planner.visualize_path(optimal_path)
        planner.print_maze_with_path(visual_matrix)
        
        # 分析结果
        planner.analyze_path(max_resource, optimal_path)
        
    except FileNotFoundError:
        print("7x7迷宫文件未找到，跳过此测试")
    
    print("\n" + "="*60 + "\n")
    
    # 测试用例2：15x15迷宫
    print("【测试用例2】15x15 迷宫资源收集")
    try:
        maze_15x15 = load_maze_from_json('perfect_maze_15x15.json')
        
        # 定义更复杂的资源分布
        resources_15x15 = {
            (2, 3): 4,    (4, 7): 6,    (6, 2): 3,
            (8, 5): 8,    (10, 9): 5,   (12, 4): 7,
            (7, 11): 4,   (3, 12): 6,   (11, 7): 5,
            (5, 13): 9,   # 高价值但可能路径较远
        }
        
        # 定义更多陷阱
        traps_15x15 = [
            (3, 4), (5, 8), (7, 3), (9, 10), (11, 6), (6, 12)
        ]
        
        # 设置环境
        planner.setup_environment(
            maze_matrix=maze_15x15,
            resources=resources_15x15,
            traps=traps_15x15,
            start_pos=(1, 1),
            exit_pos=(13, 13)
        )
        
        # 寻找最优路径
        max_resource, optimal_path = planner.find_optimal_path()
        
        # 可视化结果
        visual_matrix = planner.visualize_path(optimal_path)
        planner.print_maze_with_path(visual_matrix)
        
        # 分析结果
        planner.analyze_path(max_resource, optimal_path)
        
    except FileNotFoundError:
        print("15x15迷宫文件未找到，跳过此测试")


if __name__ == "__main__":
    demo_resource_planning() 